/**
 * ************************************************************************
 * 项目名称: projectweb <br>
 * 文件名称:  <br>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br>
 * 文件创建：1913040634刘世锦  <br>
 * 创建时间: 2021/2/5 <br>
 * 山西优逸客科技有限公司 Copyright (c) All Rights Reserved. <br>
 *
 * @version v1.0 <br>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br>
 * ************************************************************************
 */

import java.util.Arrays;

/**
 * @ProjectName: projectweb
 * @ClassName: bubblesort
 * @Description: wawawa
 * @Author: 1913040634刘世锦
 * @Date: 2021/2/5 13:45
 * @version v1.0
 * Copyright (c) All Rights Reserved,山西优逸客科技有限公司,. 
 */
public class Sort {
//二分查找
    public  static int binarySearch ( int [] arr , int n) {  //使用前提： 该数组须有序
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
                int mid = (left + right) / 2;
                if (n < arr[mid]) {
                    right = mid - 1;
                } else if (n > arr[mid]) {
                    left = mid + 1;
                } else if (arr[mid] == n) {
                    return mid + 1;
                }
        }
        return -1;// 无序 则失败
    }

//冒泡排序
    public  static  void bubblesort (int [] arr){
        int t = 0;
        for (int i = 0; i <arr.length-1 ; i++) {
            for (int j = 0; j <arr.length-1-i ; j++) {
                if(arr[j]>arr[j+1]){
                    t = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1]  = t;
                }
            }
        }
        System.out.println("冒泡排序" +Arrays.toString(arr));
    }
//插入排序
public  static void  insertSort(int [] arr){
    for (int i = 1; i <arr.length ; i++) {  //从 1开始是因为 默认第第零个的数已有序 《只有一个数当然有序啊》
        int insertn = arr[i];  // 要插入的数
        int j = i -1;      //要插入的数的  前一个数 的位置
        while (j >= 0&& insertn < arr[j]){
            arr[j+1]  =  arr[j];
            j--;
        }
        arr[j+1] = insertn;  // 为什么不把这一步放在while 里面？？？
        // 因为 可以继续判断左边是否还有 比insertn 更大的数  有的话 继续交换
        // 还有   此时这个j 已经 j--了  所以要 加1
    }
    System.out.println("插入排序" +Arrays.toString(arr));
}

// 快排
    public static void quickSort(int [] arr,int start,int end){

        if(start>=end) { //只剩一个元素不用处理直接结束。
            // 这个   需要判断 i 与 j 的 关系   ：：  在定义数组的  初始位置 跟  结束位置  时需要 定义他们之间的大小关系，
            return;
        }
        int key ,i,j ,t;

        i = start;  j = end;
        key = arr[i];

        while (i<j){

            while( arr[j]>=key &&i<j ){
                    j--;
                }
            arr[i] = arr[j];  //找到 比 key小的  赋给arr[i]
            while(arr[i]<= key &&i<j){
                    i++;
                }
            arr[j] = arr[i]; //找到 比 key大的  与之交换
            arr[i] = key;    // 把 key 放在 中间该放的位置
        }


        System.out.println("快排" +Arrays.toString(arr));// 很奇怪，没有出现过程是因为 交换的时候是直接让  arr[i] 与 arr[j] 交换
        // 而不是 先将 arr[j] 与 key 交换  ，之后再将key与 arr[i] 交换
      quickSort(arr,start,i-1);
      quickSort(arr,i+1,end);


    }
// 希尔排序
    public static void Shellsort( int [] arr){
        int dr = arr.length / 2;
        while(dr >= 1){
            Shellinsertsort(arr, dr);
            dr = dr / 2 ;
        }

      System.out.println("希尔排序" +Arrays.toString(arr));
    }
// shell
    private static void Shellinsertsort(int[] arr, int dr) { ////类似插入排序，只是插入排序增量是 1，这里增量是 dk,把 1 换成 dk 就可以了
        for (int i = dr; i <arr.length ; i++) {
           // if (arr[i] < arr[i - dr]) {   /////  /// 这个必须得写  因为分组之后 得去判断 组内的数的顺序
                int j = i - dr; //前面的数
                int insertn = arr[i]; // 要插入的数
                while (j >= 0 && insertn < arr[j]) {
                    arr[j + dr] = arr[j];
                    j -= dr;
                }
                arr[j + dr] = insertn;  // 谁他娘的 要用 arr【i】??? cao
           // }
        }

    }

//归并排序
    public static void mergesort(int [] arr, int l,int r  ){

            int m = (l + r) / 2;
            if(l < r){
            // 分
            mergesort(arr,l,m);
            mergesort(arr,m+1,r);
            //归并
            merge(arr, l,m,r );
        }
        System.out.println("归并排序" + Arrays.toString(arr));
    }

    private static void merge(int[] arr, int l, int m, int r) {
        int [] temp = new int[1+(r-l) ];  //数组的个数要一致
        int i = l;
        int j = m+1;
        int t = 0;
//        if(i>=j){
//            return;
//        }
        while(i<=m && j<=r ) {  // 比较 两段的 数组  谁小 就把谁放进来
            if (arr[i] < arr[j]) {
                temp[t] = arr[i];
                t++;   i++;
            }else{
                temp[t] = arr[j];
                t++;   j++;
            }
        }
        while (i <= m){  // if 多次i++ 之后 仍小于m  说明 有剩余的 ， 将剩余的数 （肯定是有序的） 放进 temp 中
            temp[t] = arr[i];
            t++; i++;
        }
        while (j<=r){
            temp[t++] = arr[j++]; //与 i《=m 同理

        }
        for (int n = 0; n <temp.length ; n++) {
            arr[n+l] = temp[n];
        }

    }

    public static void main(String[] args) {
         int [] arr = {6,9,7,2,1,3,5,16,4,8,36,13,44,1};

        System.out.println("原数组" + Arrays.toString(arr));
        System.out.println(exist(arr));

        // Arrays.sort(arr);
        //bubblesort( arr);
        //insertSort(arr);
        int result =   binarySearch(arr,5);
        if(result == -1){
            System.out.println("该数不存在 或是 该数组不是有序的 ");
        }
        //System.out.println( "5 所在的位置是 "+result +"");
        quickSort(arr,0,arr.length-1);
        System.out.println("-------------------==");
        //Shellsort(arr);

//        mergesort(arr,0,arr.length-1);
    }

// 局部最小值问题
    public static int exist(int[] sortedArr) {
        if (sortedArr == null || sortedArr.length == 0) {
            return -2 ;
        }
        int L = 0;
        int R = sortedArr.length - 1;
        int mid = 0;
        int num = 0;
        while (L <= R) {
            mid = L + ((R - L) >> 1); // 万一 L与R 分别是 10亿和20亿, 会出错
            if (sortedArr[mid]<= sortedArr[mid+1]&&sortedArr[mid]<= sortedArr[mid-1]) {
                return sortedArr[mid];
            } else if (sortedArr[mid] > sortedArr[mid-1]) {
                R = mid - 1;
            } else if (sortedArr[mid] > sortedArr[mid+1]) {
                L = mid + 1;
            }
        }
        return -1;
    }
}
